package com.njupt.twoStage.BinarySearch;

import java.util.Scanner;

public class ChessProblem {

    private int size;           //棋盘行与列的高度
    private int[][] board;      //定义棋盘
    private int specialRow;     //特殊点横坐标
    private int specialCol;     //特殊点列坐标
    private int number;         //L型编号

    //构造方法初始化成员变量
    public ChessProblem(int size, int specialRow, int specialCol) {
        this.size = size;
        this.board = new int[size][size];
        this.specialRow = specialRow;
        this.specialCol = specialCol;
        this.number = 0;
    }

    //解决棋盘问题的入口方法
    public void solveChessboard() {
        fillChessboard(0, 0, size, specialRow, specialCol);
    }

    /**
     *分治法 递归解决棋盘问题
     * @param row 矩阵的左边起点行下标
     * @param col 矩阵右边起点的列下标
     * @param size
     * @param specialRow
     * @param specialCol
     */
    private void fillChessboard(int row, int col, int size, int specialRow, int specialCol) {
        //递归结束的条件
        if (size == 1) {
            return;
        }

        int subSize = size / 2;
        number++;

        // 检查特殊点位于哪个象限
        boolean isSpecialInUpperHalf = specialRow < row + subSize;
        boolean isSpecialInLeftHalf = specialCol < col + subSize;

        if (isSpecialInUpperHalf && isSpecialInLeftHalf) {
            // 特殊点在左上象限
            fillChessboard(row, col, subSize, specialRow, specialCol);
        } else {
            // 特殊点不在左上象限，设置特殊点在左上象限的右下角
            board[row + subSize - 1][col + subSize - 1] = number;
            fillChessboard(row, col, subSize, row + subSize - 1, col + subSize - 1);
        }

        if (isSpecialInUpperHalf && !isSpecialInLeftHalf) {
            // 特殊点在右上象限
            fillChessboard(row, col + subSize, subSize, specialRow, specialCol);
        } else {
            // 特殊点不在右上象限，设置特殊点在右上象限的左下角
            board[row + subSize - 1][col + subSize] = number;
            fillChessboard(row, col + subSize, subSize, row + subSize - 1, col + subSize);
        }

        if (!isSpecialInUpperHalf && isSpecialInLeftHalf) {
            // 特殊点在右下象限
            fillChessboard(row + subSize, col, subSize, specialRow, specialCol);
        } else {
            board[row + subSize][col + subSize - 1] = number;
            fillChessboard(row + subSize, col, subSize, row + subSize, col + subSize - 1);
        }

        if (!isSpecialInUpperHalf && !isSpecialInLeftHalf) {
            fillChessboard(row + subSize, col + subSize, subSize, specialRow, specialCol);
        } else {
            // 特殊点不在右下象限，设置特殊点在右下象限的左上角
            board[row + subSize][col + subSize] = number;
            fillChessboard(row + subSize, col + subSize, subSize, row + subSize, col + subSize);
        }
    }

    // 打印棋盘
    public void printBoard() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(board[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入棋盘的大小：");
        int N = scanner.nextInt();

        System.out.println("请输入特殊方格的行号和列号（从1开始计数）：");
        int specialRow = scanner.nextInt() - 1;
        int specialCol = scanner.nextInt() - 1;


       ChessProblem chessProblem = new ChessProblem(N, specialRow, specialCol);

        System.out.println("原始棋盘：");
        chessProblem.solveChessboard();
        chessProblem.board[specialRow][specialCol] = -1;
        chessProblem.printBoard();
    }
}
